package array;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedHashSet;

public class Array {
    /**
     * 寻找数组的中心索引
     */

    public int pivotIndex(int[] nums) {
        int suml = 0;
        int sumr = 0;
        for (int i = 0; i < nums.length - i - 1; i++){
            suml += nums[i];
            sumr += nums[nums.length - i - 1];
        }
        sumr += suml;
        suml = 0;
        if (nums.length % 2 == 1){
            sumr +=nums[nums.length / 2];
        }

        for (int i = 0; i < nums.length; i++){
            sumr -= nums[i];
            if (suml == sumr )
            {
                return i;
            }
            suml += nums[i];
        }
        return -1;
    }
    /**
     * 搜索插入位置
     */
    public int searchInsert(int[] nums, int target) {
        return search(nums,0,nums.length - 1,target);
    }
    int search(int[] nums,int left,int right, int target){
        if(left > right){
            return left;
        }
        if(target <= nums[(left+right)/2])
            return search(nums,left,(left+right)/2 - 1,target);
        else{
            return search(nums,(left+right)/2 + 1,right ,target);
        }
    }

    /**
     * 合并区间
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1){
            return intervals;
        }
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] arr1,  int[] arr2){
                if (arr1[0] < arr2[0]){
                    return -1;
                }
                else if (arr1[0] > arr2[0]){
                    return 1;
                }
                else if (arr1[1] == arr2[1]){
                    return 0;
                }
                else if(arr1[1] < arr2[1]){
                    return -1;
                }
                else {
                    return 1;
                }
            }
        });
        LinkedHashSet<int[]> set = new LinkedHashSet();

        boolean isAdd = true;
        for (int i = 0; i < intervals.length - 1; i++){
            boolean add2 =true;
            if(i < intervals.length - 1 && intervals[i][1] >= intervals[i+1][0]){
                add2 = false;
                int min = intervals[i][0];
                int max = intervals[i][1];
                boolean k = true;
                do{
                    if(max <= intervals[i+1][1]){
                        max = intervals[i+1][1];
                    }
                    i++;
                    if(i == intervals.length -1){
                        isAdd = false;
                    }
                }while(i < intervals.length - 1 && max >= intervals[i+1][0]);
                set.add(new int[]{min,max});
            }


            if(add2){
                set.add(intervals[i]);}
        }
        if (isAdd){set.add(intervals[intervals.length - 1]);}
        int[][] arr = new int[set.size()][2];

        int flag = 0;
        for(int[] arr0 : set){
            arr[flag] = arr0;
            flag++;
        }
        return arr;
    }
}
